题目大意
题目链接
一个无限大的二维图， 从(0, 0)出发，走n步，只能向右和向下走， 不能在同一方向连续走k步，问走n步，不同路径的方案数（对1e9+7取余）。
分析
dp[i] 表示第i步向下走的方案数。
sum = dp[1] + dp[2] + … + dp[n]
dp[i] 也可以表示第i步向右走的方案数。
所以最后答案就是 sum * 2
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
inline ll read() {
ll res = 0;bool f = 0;char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getchar();}
while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0';ch = getchar();}
return f ? (~res + 1) : res;
}
ll sum, dp[N];
int main(){
int t = read();
while(t--){
int n = read(), k = read();
dp[1] = sum = 1;
for (int i = 2; i <= n; ++i){
dp[i] = sum;
if (i > k){
sum += mod - dp[i - k];
sum %= mod;
}
sum += dp[i];
sum %= mod;
}
if (n) cout << sum * 2 % mod << "\n";
else puts("1");
}
return 0;
}
|
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。 --mingfuyan
千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。